# 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
#
#  示例 1：
# 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
# 输出：6
# 解释：最大矩形如上图所示。
#
#  示例 2：
# 输入：matrix = []
# 输出：0
#
#  示例 3：
# 输入：matrix = [["0"]]
# 输出：0
#
#  示例 4：
# 输入：matrix = [["1"]]
# 输出：1
from typing import List


class Solution:
    def maximalRectangle2(self, matrix: List[List[str]]) -> int:
        """
        该问题可以转化成 84 柱状图中最大的矩形
        将二维矩阵的每列中 '1' 的总高度看成该层列的高度，即可将该问题转化成逐层求 84 的问题
        :param matrix:
        :return:
        """
        m, n, res = len(matrix), len(matrix[0]), 0
        heights = [0] * n

        def largestRectangleArea() -> int:
            lefts, rights, stack, tmpMaxRes = [0] * n, [0] * n, [], 0  # lefts[i]表示 heights[i] 的左边界，rights[i]表示 heights[i] 的右边界
            for i, h in enumerate(heights):  # 顺序遍历求每个宽度的左边界
                while stack and heights[stack[-1]] >= h:  # 把所有高度大于等于当前高度 h 的值全部移除
                    stack.pop()
                lefts[i] = stack[-1] if stack else -1  # 特殊情况是栈中所有的值都比当前height[i]大，该元素宽度的左边界为 -1(哨兵)
                stack.append(i)
            stack.clear()

            for i in range(n - 1, -1, -1):  # 倒序遍历求每个宽度的右边界
                while stack and heights[stack[-1]] >= heights[i]:  # 把所有高度大于等于当前高度 h 的值全部移除
                    stack.pop()
                rights[i] = stack[-1] if stack else n  # 特殊情况是栈中所有的值都比当前height[i]大，该元素宽度的右边界为 n(哨兵)
                stack.append(i)

            for i, h in enumerate(heights):
                tmpMaxRes = max(tmpMaxRes, h * (rights[i] - lefts[i] - 1))
            return tmpMaxRes

        for row in range(m):
            for col in range(n):
                heights[col] = 0 if matrix[row][col] == '0' else heights[col] + 1
            res = max(res, largestRectangleArea())  # 每计算完一层的 heights 就要计算一次该层的最大矩形面积

        return res

    def maximalRectangle1(self, matrix: List[List[str]]) -> int:
        """
        暴力法的优化
        暴力法:枚举所有可能的矩形判断该矩形是否是全 '1' 的，如果是则更新(超时)

        优化:
            先计算出每个元素在当前行左边的连续 '1'的个数
            然后再再这个的基础上依次遍历可能的高，得到当前元素的最大矩形面积
        :param matrix:
        :return:
        """
        m, n, res = len(matrix), len(matrix[0]), 0
        lefts = [[0] * n for _ in range(m)]  # lefts[i][j] 为矩阵第 i 行第 j 列元素的左边连续 1 的数量
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '1':
                    lefts[i][j] = lefts[i][j - 1] + 1 if j > 0 else 1
        # 遍历矩阵计算以 (i, j) 为右下角的最大矩阵
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '1':
                    width = lefts[i][j]  # 初始化以 (i, j) 为右下角的最大矩形面积(此时高度为1)
                    for k in range(i, -1, -1):  # 依次向上扩展高度，并计算可能的最大矩形面积
                        width, height = min(width, lefts[k][j]), (i - k + 1)
                        res = max(res, width * height)
        return res

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        return self.maximalRectangle2(matrix)


if __name__ == '__main__':
    matrix = [
        ["1", "0", "1", "0", "0"],
        ["1", "0", "1", "1", "1"],
        ["1", "1", "1", "1", "1"],
        ["1", "0", "0", "1", "0"]]
    print(Solution().maximalRectangle(matrix))
